The present application relates generally to an improved data processing apparatus and method and more specifically to mechanisms for leasing fragmented storage between processes.
Fragmentation is a phenomenon in which free storage becomes divided into many small pieces over time. Fragmentation is a weakness of certain storage allocation algorithms, occurring when an application allocates and de-allocates regions of storage of varying sizes, and the allocation algorithm responds by leaving the allocated and de-allocated regions interspersed. The result is that although free storage is available, it is effectively unusable because it is divided into pieces that are too small to satisfy the demands of the application. The term “external” refers to the fact that the unusable storage is outside the allocated regions.
For example, in dynamic memory allocation, a block of 1000 bytes might be requested, but the largest contiguous block of free space has only 300 bytes. Even if there are ten blocks of 300 bytes of free space, separated by allocated regions, one still cannot allocate the requested block of 1000 bytes, and the allocation request will fail. Fragmentation also occurs in file systems as many files of different sizes are created, change size, and are deleted. The effect is even worse if a file that is divided into many small pieces is deleted, because this leaves similarly small regions of free spaces.
Modern computer systems have memory management units that avoid fragmentation by creating a more granular allocation strategy or by providing abstraction that makes virtual memory addresses appear contiguous even when physical addresses cannot be. This usually results in higher latency due to extra cycles needed to accomplish the allocation strategy. In normal operating environments, fragmentation continues to occur.